#include <stdio.h>

typedef int ElementType;
#define NotFound (-1)

/* START: fig2_9.txt */
int BinarySearch(const ElementType A[], ElementType X, int N) {
	int Low, Mid, High;

	/* 1*/Low = 0;
	High = N - 1;
	/* 2*/while (Low <= High) {
		/* 3*/Mid = (Low + High) / 2;
		/* 4*/if (A[Mid] < X)
			/* 5*/Low = Mid + 1;
		else
		/* 6*/if (A[Mid] > X)
			/* 7*/High = Mid - 1;
		else
			/* 8*/return Mid; /* Found */
	}
	/* 9*/return NotFound; /* NotFound is defined as -1 */
}
/* END */

main() {
	static int A[] = { 1, 3, 5, 7, 9, 13, 15 };
	const int SizeofA = sizeof(A) / sizeof(A[0]);
	int i;

	for (i = 0; i < 20; i++)
		printf("BinarySearch of %d returns %d\n", i,
				BinarySearch(A, i, SizeofA));
	return 0;
}
